// 331.验证二叉树的前序序列化
package Leetcode_Second_Brush;

import java.util.Deque;
import java.util.LinkedList;

public class Solution331 {
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        Deque<String> stack = new LinkedList<>();

        for (String node : nodes) {
            while ("#".equals(node) && !stack.isEmpty() && "#".equals(stack.peek())) {
                stack.pop(); // 移除 #
                if (stack.isEmpty()) {
                    return false; // 若栈为空，返回 false
                }
                stack.pop(); // 移除其父节点
            }
            stack.push(node); // 将当前节点推入栈中
        }

        // 栈中应仅剩一个 # 才是有效的序列化
        return stack.size() == 1 && "#".equals(stack.peek());
    }

}
